﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace T16Generic
{
    class Program
    {
        static void Main(string[] args)
        {
            //泛型具体：类型安全
            BtreeNode<string> root =new BtreeNode<string>("北京");
            root.Left = new BtreeNode<string>("石家庄");
            root.Right = new BtreeNode<string>("济南");
            root.Left.Left = new BtreeNode<string>("太原");
            root.Right.Left = new BtreeNode<string>("徐州");
            root.Left.Right= new BtreeNode<string>("郑州");
            root.Right.Right = new BtreeNode<string>("青岛");
            root.Left.Right.Left = new BtreeNode<string>("西安");
            root.Left.Right.Right = new BtreeNode<string>("武汉");
            root.Right.Left.Left = new BtreeNode<string>("南京");
            root.Right.Left.Right = new BtreeNode<string>("连云港");
            Console.WriteLine("\n前序遍历");
            root.PreorderTraverse();
            Console.WriteLine("\n后序遍历");
            root.PostTraverse();


            BtreeNode<int> root2 = new BtreeNode<int>(0);
            root2.Left = new BtreeNode<int>(-1);
            root2.Right = new BtreeNode<int>(1);
            root2.Right.Right = new BtreeNode<int>(2);
            Console.WriteLine("\n中序遍历");
            root2.InorderTraverse();
            BtreeNode<int> node = root2 << 2;
            Console.WriteLine(node);
            Console.WriteLine("\n中序遍历");
            node.InorderTraverse();


            Console.ReadKey();
        }
    }
    /// <summary>
    /// 二叉树泛型实现
    /// </summary>
    /// <typeparam name="T"></typeparam>
    public class BtreeNode<T>
    {
        private T data;
        public T Data
        {
            get { return data; }
            set {
                if (!data.Equals(value))//说明T必须实现了Equals
                    data = value;
                 }
        }
        //递归定义
        public BtreeNode<T> Left { get; set; }
        public BtreeNode<T> Right { get; set; }
        public BtreeNode(T data)
            {
             this.data=data;
            }
/// <summary>
 /// 先序遍历
 /// </summary>
    public void PreorderTraverse()
    {
    Console.Write(this.data.ToString()+' ');
            if (this.Left != null)
                this.Left.PreorderTraverse();
            if (this.Right != null)
                this.Right.PreorderTraverse();
        
    }
        /// <summary>
        /// 中序遍历
        /// </summary>
        public void InorderTraverse()
    {
            if (this.Left != null)
                this.Left.InorderTraverse();
            Console.Write(this.data.ToString()+' ');
            if (this.Right != null)
                this.Right.InorderTraverse();
        }
        /// <summary>
        /// 后序遍历
        /// </summary>
        public void PostTraverse()
        {
            if (this.Left != null)
                this.Left.InorderTraverse();
           
            if (this.Right != null)
                this.Right.InorderTraverse();
            Console.Write(this.data.ToString() + ' ');
        }
        /// <summary>
        /// 获取第N层的左子树
        /// </summary>
        /// <param name="node"></param>
        /// <param name="n"></param>
        /// <returns></returns>
public static BtreeNode<T> operator <<(BtreeNode<T> node,int n)
        {
            for (int i = 0; i < n&&node.Left!=null; i++)
            {
                node = node.Left;
            }
            return node;
        }
        /// <summary>
        /// 获取第N层的右子树
        /// </summary>
        /// <param name="node"></param>
        /// <param name="n"></param>
        /// <returns></returns>
        public static BtreeNode<T> operator >>(BtreeNode<T> node, int n)
        {
            for (int i = 0; i < n && node.Right != null; i++)
            {
                node = node.Right;
            }
            return node;
        }



        public override string ToString()
        {
            return data.ToString();
        }
    }
}
